package demo3LinkList.MyNodeAndMyList;


/**
 * @Author shenxinyuan
 * @Description //TODO 自定义 单链表
 * @Date $ time$ 2021/7/21
 * @Param
 * @return
 **/
public class NodeList<T extends Comparable<T>> implements List<T> {
    //如果T类型不是Number类及其子类，那么这种类一定要继承Comparable接口重写compareTo()方法
    private Node<T> head;   //默认head=null
    private Node<T> tail;


    //O(1时间复杂度删除结点)

    /**
     * @return void
     * @Author shenxinyuan
     * @Description //TODO
     * @Date 2021/7/21
     * @Param [dest]要删除的目标结点
     * 待删指针不是尾指针：
     * 待删指针的值用待删指针的下一个指针的值覆盖
     * 删掉待删指针的下一个指针
     * 待删指针是尾指针：
     * 待删指针同时是头指针：
     * 删掉头指针
     * 待删指针不是头指针
     * 找到待删指针的前一个指针
     * 删掉待删指针，前一个指针的next赋值为空
     **/
    public boolean deleteO1(Node dest) {
        boolean res = false;
        if (dest == null) {
            System.out.println("要删除的节点不合法！");
            return res;
        }

        if (dest != tail) {             //要删除的节点不是尾节点
            Node next = dest.getNext();
            dest.setValue(next.getValue());

            //删除后继结点
            dest.setNext(next.getNext());
            next.setNext(null);
            res = true;

        } else if (head == dest) {           //要删除的节针是尾指针且是头节点
            head = tail = null;
            res = true;

        } else {                         //要删除的节点是尾节点但不是头结点
            Node p = head.getNext();
            while (p != dest) {
                p = p.getNext();
            }
            p.setNext(dest.getNext());
            dest.setNext(null);     //用于垃圾回收
            res = true;
        }

        return res;


    }


    //造出有环的链表
    public void makeCircle(int target) {      //为了exercise11的QuikAndSlowQuotation写的功能
        int i = 0;
        Node temp = head;
        if (temp != null) {
            do {
                i++;
                if (target == i - 1) {
                    tail.setNext(temp);
                    break;
                }
                temp = temp.getNext();
            } while (temp != null);
        }
    }

    //找到有环链表的相遇节点
    public Node<T> findMeetPoint() {         //为了exercise11的QuikAndSlowQuotation写的功能
        if (head == tail) {
            return null;
        }
        Node<T> slow = head;
        Node<T> fast = head;
        while (fast.getNext() != null) {
            fast = fast.getNext().getNext();
            slow = slow.getNext();
            if (fast == slow) {
                return fast;
            }
        }
        return null;
    }

    //调用该方法的前提是确认有环，找到有环链表的入口节点
    public Node<T> entranceNode(Node<T> meetPoint) {
        Node<T> slow = head;
        Node<T> fast = meetPoint;
        while (slow != fast) {
            slow = slow.getNext();
            fast = fast.getNext();
        }
        return fast;
    }


    //造出相交链表
    public void makeCircle(NodeList<T> aim, int index) {      //为了exercise11的IntersectingLinkedList写的功能
        int i = 0;
        Node temp = head;
        if (temp != null) {
            do {
                i++;
                if (index == i - 1) {
                    aim.tail.setNext(temp);
                    aim.tail = this.tail;
                    break;
                }
                temp = temp.getNext();
            } while (temp != null);
        }
    }

    //寻找相交链表的相交节点
    public Node<T> findMeetPoint(NodeList<T> aim, int Dvalue) {
        //空链表则返回,单链表的tail不相同肯定不相交
        if (head == tail || aim.head == aim.tail || this.tail != aim.tail) {
            return null;
        }
        int temp = 0;
        Node<T> shot;
        Node<T> lng;
        if (this.size() > aim.size()) {
            shot = aim.head;
            lng = this.head;
        } else {
            shot = this.head;
            lng = aim.head;
        }
        //长的单链表先走差值
        while (temp < Dvalue && Dvalue != 0) {
            lng = lng.getNext();
            temp++;
        }
        //然后开始寻找交点
        while (lng != null) {
            if (lng.getValue().compareTo(shot.getValue()) == 0) {
                return shot;
            }
            shot = shot.getNext();
            lng = lng.getNext();
        }
        return null;
    }

    //与另一个有序链表合并
    public NodeList<T> merge(NodeList<T> list) {
        Node<T> node = null;
        Node<T> temp = null;
        Node<T> p = null;
        Node<T> q = null;
        if (this.head.getValue().compareTo(list.head.getValue()) <= 0) {
            node = this.head;
            temp = list.head;
        } else {
            node = list.head;
            temp = this.head;
        }
        //方便返回
        this.head = node;
        //开始链接
        while (node != null && temp != null) {
            p = node.getNext();
            if (p == null) {              //如果node所在的链表提前遍历结束，直接脸上另一个链表temp所在位置即可，如果temp所在链表先结束node无需更新
                node.setNext(temp);
                break;
            }
            if (p.getValue().compareTo(temp.getValue()) <= 0) {
                node = p;
            } else {
                node.setNext(temp);
                temp = p;
                node = node.getNext();
            }
        }

        //连接上没有连完的

        return this;
    }

    //方法一：采用头插法逆置链表
    public void reverse1() {
//        System.out.println("yuewf");
        Node<T> p;                  //p是第一个指针
        Node<T> q = null;           //q是继p之后的指针
        Node<T> s = null;           //s是继q之后的指针
        Node<T> newHead = null;     //新的头结点
        if (size() == 0 || size() == 1) {
            return;
        } else {
            p = head;
            q = p.getNext();
            s = q.getNext();
            while (q != null) {             //防止空指针
                q.setNext(p);
                p = q;
                newHead = p;
                q = s;
                if (s != null) {        //防止空指针
                    s = s.getNext();
                }
            }
            head.setNext(null);     //更新head结点
            head = newHead;
        }
    }

    //方法二：逆置单链表，减少了newHead的定义
    //利用中间变量，直接修改next的指向，更新head
    //思想与头插法不同，实现代码想类似
    public void reverse2() {
        Node<T> p;
        Node<T> q = null;
        Node<T> s = null;
        if (size() == 0 || size() == 1) {
            return;
        } else {
            p = head;
            q = p.getNext();
            s = q.getNext();
            while (q != null) {  //先翻转next的指向
                q.setNext(p);
                p = q;
                q = s;
                if (s != null) {
                    s = s.getNext();
                }
            }
            //调换头尾
            head.setNext(null);
            head = p;
        }
    }


    @Override
    public int size() {
        int result = 0;
        Node temp = head;
        if (head == null) {
            return 0;
        } else {
            result++;
            while (temp.getNext() != null) {
                temp = temp.getNext();
                result++;
            }
        }
        return result;
    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public void addHead(T value) {
        Node<T> newNode = new Node<>(value);

        newNode.setNext(this.head);

        //更新新的的头结点
        head = newNode;
        if (head.getNext() == null) {     //链表为空时
            tail = newNode;     //链表只剩头部的情况
        }
    }

    @Override
    public void addTail(T value) {
        Node<T> newNode = new Node<>(value);
        Node<T> temp = head;

        if (head != null) {
            for (; temp.getNext() != null; temp = temp.getNext()) {

            }
            temp.setNext(newNode);
        } else {
            head = newNode;
        }
        tail = newNode;     //更新尾巴
    }

    @Override
    public T getValue(int index) {
        return null;
    }

    @Override
    public void removeHead() {

    }

    @Override
    public void removeTail() {

    }

    @Override
    public void removeIndex(int x) {

    }

    @Override
    public boolean removeValue(T value) {
        return false;
    }

    @Override
    public boolean changeValue(T src, T aim) {
        return false;
    }

    @Override
    public int searchValue(T value) {
        return 0;
    }

    @Override
    public boolean contain(T value) {
        return false;
    }

    @Override
    public void show() {
        Node<T> temp = head;
        if (temp == null) {
            System.out.print("链表为空！");
        } else {
            while (temp != null) {
                System.out.print(temp.getValue() + " ");
                temp = temp.getNext();
            }
        }
        System.out.println();
    }

    @Override
    public Node getNode(T value) {
        Node dest = null;

        if(head == null||tail == null){
            return null;
        }
        Node p = head;
        do{
            if(p.getValue() == value){
                dest = p;
                break;
            }
            p=p.getNext();
        }while(p!=null);

        return dest;
    }
}
